#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

typedef int ElemType;
typedef struct LNode
{
    ElemType data;
    struct LNode *prior;
    struct LNode *next;
} LNode, *LinkList;

class DList
{
public:
    DList();
    ~DList();
    void initList();
    void printList();
    //insert
    bool insertPNext(LinkList p, ElemType e);
    bool insertPos(int pos, ElemType e);
    //delete
    bool deletePNext(LinkList p, ElemType &e);
    bool deletePos(int pos, ElemType &e);
private:
    LinkList head;
};

DList::DList()
{
    initList();
}
DList::~DList()
{
    LinkList p = head;
    if (p != NULL)
    {
        while (p->next != NULL)
        {
            LinkList q = p->next;
            if (q->next != NULL)
                q->next->prior = p;
            p->next = q->next;
            q->prior = NULL;
            q->next = NULL;
            free(q);
        }
        free(p);
    }
    head = NULL;
}

void DList::initList()
{
    head = NULL;
}

void DList::printList()
{
    if (head == NULL)
    {
        printf("The List is empty\n");
        return;
    }
    LinkList p = head;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

bool DList::insertPNext(LinkList p, ElemType e)
{
    if (p == NULL)
        return false;
    LinkList q = (LNode *)malloc(sizeof(LNode));
    q->data = e;

    if (p->next != NULL)
        p->next->prior = q;
    q->next = p->next;
    p->next = q;
    q->prior = p;

    return true;
}

bool DList::insertPos(int pos, ElemType e)
{
    if (pos < 1)
    {
        printf("insert pos error\n");   
        return false;
    }
    if (head == NULL && pos != 1)
    {
        printf("empty list, insert pos error\n");
        return false;
    }
    LinkList p = head;
    int j = 1;
    if (pos == 1)
    {
        LinkList q = (LNode *)malloc(sizeof(LNode));
        q->data = e;
        q->next = NULL;
        q->prior = NULL;
        if (head != NULL)
        {
            q->next = p;
            q->prior = p->prior;
            p->prior = q;
        }
        head = q;
        return true;
    }
    while (p != NULL && j < pos-1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL)
        return false;
    return insertPNext(p, e);
}

bool DList::deletePNext(LinkList p, ElemType &e)
{
    if (p->next == NULL && p == NULL)
        return false;

    LinkList q = p->next;
    e = q->data;
    if (q->next != NULL)
        q->next->prior = p;
    p->next = q->next;
    q->prior = NULL;
    q->next = NULL;
    free(q);
    printf("done.\n");
    return true;
}

bool DList::deletePos(int pos, ElemType &e)
{
    if (pos < 1)
        return false;
    LinkList p = head;
    if (p == NULL)
        return false;
    if (pos == 1)
    {
        LinkList q = head;
        e = q->data;
        head = q->next;
        if (head != NULL)
            head->prior = NULL;
        q->next = NULL;
        q->prior = NULL;
        free(q);
        printf("done.\n");
        return true;
    }
    //find pos-1
    int j = 1;
    while (p != NULL && j < pos-1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL)
        return false;
    return deletePNext(p,e);
}

void menu()
{
    printf("1. insertPos\n");
    printf("2. deletePos\n");
    printf("p. print\n");
}

void start(DList &dlist, char c)
{
    int pos;
    ElemType e;
    switch (c)
    {
    case '1':
        printf("Please input the position and the element you want to insert:\n");
        scanf("%d %d", &pos, &e);
        dlist.insertPos(pos, e);
        break;
    case '2':
        printf("Please input the position you want to delete:\n");
        scanf("%d", &pos);
        dlist.deletePos(pos, e);
        break;
    case 'p':
        dlist.printList();
        break;
    case 'q':
        break;
    default:
        menu();
        break;
    }
}
int main()
{
    DList dlist;

    char c = ' ';
    while (c != 'q')
    {
        scanf("%c", &c);
        start(dlist, c);
    }
    return 0;
}
